﻿// owner 蒋家伟

#pragma once
#include <type_traits>
#include <vector>
#include <functional>

namespace jsdk
{
    // 类别描述 ：二分数组，依赖于排序后的结果可以进行二分查找
    // note :    可以做近似的模糊查找到最接近的结果
    // ValueType 存储值类型
    // CompareLess 小于比较仿函数, 默认使用std::less
    // CompareEqual 相等的仿函数,  默认使用std::equal

    enum class CompareResult : int8_t
    {
        Error =-1,                          // 如果觉得左右两侧值都不合适，则选择Error返回
        Left = 0,                           // 左侧的值近似
        Right = 1                           // 右侧的值近似
    };

    template<typename ValueType, typename CompareLess = std::less<ValueType>, typename CompareEqual = std::equal_to<ValueType>>
    class BinaryVector
    {
        static_assert(!std::is_pointer<ValueType>::value, "值类型不期望是指针");
        static_assert(!std::is_reference<ValueType>::value, "值类型不期望是引用");
    public:
        using valueType = typename ValueType;
        using BinaryVectorIter = typename std::vector<ValueType>::iterator;
        using const_BinaryVectorIter = typename std::vector<ValueType>::const_iterator;
        using NearestCompareFun = typename std::function<CompareResult(const ValueType& inputValue, const ValueType& leftValue, const ValueType& rightValue)>;
        static CompareResult defaultComareResult(const ValueType& inputValue, const ValueType& leftValue, const ValueType& rightValue)
        {
            return std::abs(inputValue - leftValue) < std::abs(inputValue - rightValue) ? CompareResult::Left : CompareResult::Right;
        }

    public:
        BinaryVector() {}
        ~BinaryVector() {}
        explicit BinaryVector(std::vector<ValueType>&& valueVecs)
        {
            m_dataVec.swap(valueVecs);
            this->sort();
        }

        explicit BinaryVector(const std::vector<ValueType>& valueVecs)
        {
            m_dataVec = valueVecs;
            this->sort();
        }

        BinaryVector(const BinaryVector<ValueType>& binaryVec)
        {
            m_dataVec = binaryVec;
        }
        BinaryVector(BinaryVector<ValueType>&& rBinaryVec)
        {
            m_dataVec.swap(rBinaryVec);
        }

        BinaryVector& operator =(const BinaryVector<ValueType>& binaryVec)
        {
            m_dataVec = binaryVec;
            return *this;
        }

    public:
        size_t size() const
        {
            return m_dataVec.size();
        }

        void swap(BinaryVector<ValueType>& binaryVec)
        {
            m_dataVec.swap(binaryVec);
        }

        void swap(std::vector<ValueType>& valueVec)
        {
            m_dataVec.swap(valueVec);
            this->sort();
        }

        /// \ brief     找到与给定的值最相近的Index下标
        /// \ note :    如果找到相等的值时则返回其下标
        /// \ in value  模糊查找的目标值
        /// \ in fun    当找到一个近似的区间时，需要比较的回调函数,通过自定义回调表明谁更接近
        /// \ return    最近的index, 返回-1表示容器为空或者模糊查找的近似值用户自定义不想要
        int find_nearest(const ValueType& value, const NearestCompareFun& fun = BinaryVector::defaultComareResult) const
        {
            if (m_dataVec.empty())
                return -1;
            int index = binary_find_nearest(value, 0, static_cast<int>(m_dataVec.size()) - 1);

            if (index < 0 || index > m_dataVec.size() - 1)
            {
                throw "index out of range";
            }

            if (CompareEqual()(m_dataVec[index], value))
            {
                return index;
            }

            if (index == 0)
            {
                // 如果搜索的值小于当前索引的值，表示比最小的值还小，最近则为0
                if (CompareLess()(value, m_dataVec[index]))
                {
                    return index;
                }
            }

            if (index == static_cast<int>(m_dataVec.size()) - 1)
            {
                // 如果搜索的值大于最大索引的值
                if (CompareLess()(m_dataVec[index], value))
                {
                    return index;
                }

                // 修改index值，这样保证下面的index与index+1为正确的区间
                index = index - 1;
            }

            // 到这里则表示当前搜索的索引在最大与最小值中间
            CompareResult res = fun(value, m_dataVec[index], m_dataVec[index + 1]);
            if (res == CompareResult::Left)
            {
                return index;
            }
            else if (res == CompareResult::Right)
            {
                return index + 1;
            }
            else
            {
                return -1;
            }
            

            throw "not run this";
        }

        void clear()
        {
            m_dataVec.clear();
        }

        void resize(size_t size)
        {
            m_dataVec.resize(size);
        }

        void insert(const ValueType& value)
        {
            if (m_dataVec.empty())
            {
                m_dataVec.push_back(value);
                return;
            }

            int index = binary_find_nearest(value, 0, static_cast<int>(m_dataVec.size()) - 1);
            if (index < 0 || index > m_dataVec.size() - 1)
            {
                throw "index out of range";
            }
            if (CompareLess()(value, m_dataVec[index]))
            {
                m_dataVec.insert(m_dataVec.begin() + index, value);
            }
            else
            {
                m_dataVec.insert(m_dataVec.begin() + index + 1, value);
            }
        }

        void insert(ValueType&& value)
        {
            if (m_dataVec.empty())
            {
                m_dataVec.push_back(std::move(value));
                return;
            }

            int index = binary_find_nearest(value, 0, m_dataVec.size() - 1);

            if (index < 0 || index > m_dataVec.size() - 1)
            {
                throw "index out of range";
            }

            if (CompareLess()(value, m_dataVec[index]))
            {
                m_dataVec.insert(m_dataVec.begin() + index, std::move(value));
            }
            else
            {
                m_dataVec.insert(m_dataVec.begin() + index + 1, std::move(value));
            }
        }

    public:
        const_BinaryVectorIter begin() const
        {
            return m_dataVec.begin();
        }

        const_BinaryVectorIter end() const
        {
            return m_dataVec.end();
        }

        BinaryVectorIter begin()
        {
            return m_dataVec.begin();
        }

        BinaryVectorIter end()
        {
            return m_dataVec.end();
        }

    public:
        const ValueType& operator [](size_t index) const
        {
            return m_dataVec[index];
        }

        ValueType& operator [](size_t index)
        {
            return m_dataVec[index];
        }

    private:
        int binary_find_nearest(const ValueType& value, int left, int right) const
        {
            int midIndex = (left + right) / 2;
            if (left > right)
            {
                return midIndex;
            }

            // 相等返回
            if (CompareEqual()(m_dataVec[midIndex], value))
            {
                return midIndex;
            }

            if (CompareLess()(value, m_dataVec[midIndex]))
            {
                // 小于
                return this->binary_find_nearest(value, left, midIndex - 1);
            }
            else
            {
                // 大于
                return this->binary_find_nearest(value, midIndex + 1, right);
            }
        }

        void sort()
        {
            std::sort(m_dataVec.begin(), m_dataVec.end(), CompareLess());
        }

    private:
        std::vector<ValueType> m_dataVec;
    };
}
